package org.datastructure.firstday.sort;

import java.util.Arrays;

/**
 * 希尔排序本就是对插入排序的优化方案，通过差分组来高效完成插入排序
 * 如果复习的时候看不懂，可以直接去看插入排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort1(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 通过位移的方式插入排序
     *
     * @param arr
     */
    public static void shellSort1(int... arr) {

      /*  // TODO: step 1
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5; j >= 0; j -= 5) {
                if (arr[j] > arr[j + 5]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));


        // TODO: 2021/7/5 step 2

        for (int i = 2; i < arr.length; i++) {
            for (int j = i-2; j >=0; j-=2) {
                if(arr[j]>arr[j+2]){
                    int temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));

        // TODO: 2021/7/5 step 3
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >=0; j-=1) {
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));*/

        int stemp = 0;// TODO: 2021/7/6 计算步长，通过步长分组
        for (int step = arr.length / 2; step > 0; step /= 2) {
            // TODO: 2021/7/6 无序数组从左向右开始和有序数组比较
            for (int i = step; i < arr.length; i++) {
                // TODO: 2021/7/6 有序数组从右向左开始和无序数组从右向左依次比较
                for (int j = i - step; j >= 0; j -= step) {
                    // TODO: 第一次比较arr[j]=有序数组第一个元素，arr[j+step]=无序第一个元
                    if (arr[j] > arr[j + step]) {
                        stemp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = stemp;
                    }
                }
            }
        }
    }

    /**
     * 通过直接插入，实现排序
     * TODO 如果复习的时候看不懂，可以直接去看插入排序
     *
     * @param arr
     */
    public static void shellSort2(int... arr) {
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                int insertVal = arr[i];
                // TODO: 2021/7/6  有序数组右边第一个元素(考虑步长)
                int insertIndex = i - step;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + step] = arr[insertIndex];
                    insertIndex -= step;
                }
                if (insertIndex + step != i) {
                    arr[insertIndex + step] = insertVal;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}
